package com.alex.algorithm.easy;

import java.util.Stack;

public class InvertBinaryTree {

    public static void main(String[] args) {
        BinaryTreeNode root = new BinaryTreeNode();

        BinaryTreeNode n1 = new BinaryTreeNode();
        n1.setValue(1);
        root.setLeft(n1);

        BinaryTreeNode n2 = new BinaryTreeNode();
        n2.setValue(2);
        root.setRight(n2);

        BinaryTreeNode n3 = new BinaryTreeNode();
        n3.setValue(3);

        n2.setRight(n3);

        BinaryTreeNode n4 = new BinaryTreeNode();
        n4.setValue(3);
        n3.setRight(n4);

        root.traverse(root);
        System.out.println();
//        invertBinaryTree(root);
        recursion(root);
        root.traverse(root);
    }

    public static void invertBinaryTree(BinaryTreeNode root) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            BinaryTreeNode cur = stack.pop();
            BinaryTreeNode left = cur.getLeft();
            BinaryTreeNode right = cur.getRight();
            cur.setRight(left);
            cur.setLeft(right);
            if (cur.getLeft() != null) {
                stack.push(cur.getLeft());
            }
            if (cur.getRight() != null) {
                stack.push(cur.getRight());
            }
        }
    }

    public static void recursion(BinaryTreeNode root) {
        if (root != null) {
            BinaryTreeNode left = root.getLeft();
            BinaryTreeNode right = root.getRight();
            root.setRight(left);
            root.setLeft(right);
        }
        if (root.getRight() != null) {
            recursion(root.getRight());
        }
        if (root.getLeft() != null) {
            recursion(root.getLeft());
        }
    }
}
